package main.java.indi.zyj.coderecord;

public class VaildPath {

    int[] father;


    public boolean validPath(int n, int[][] edges, int source, int destination) {
        father = new int[n];
        init();
        for (int i = 0; i < edges.length; i++) {
            join(edges[i][0], edges[i][1]);
        }
        return isSame(source, destination);
    }

    // 并查集初始化
    public void init() {
        for (int i = 0; i < father.length; i++) {
            father[i] = i;
        }
    }

    // 并查集里寻根的过程
    public int find(int u) {
        if (father[u] == u) {
            return u;
        } else {
            father[u] = find(father[u]);
        }
        return father[u];
    }

    // 查询两个是否在同一个并查集里(是不是一个爸爸)
    public boolean isSame(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }

    // 将v->u 这条边加入并查集，v的爸爸是u，father[v] -> u
    public void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
        father[v] = u;
    }

}
